package MonotonicStack;

/**
 * 求一个数组中的最长坡
 *
 * @author Liaorun
 */
public class MaximumWidthRamp {

    public static void main(String[] args) {
        System.out.println(maxWidthRamp(new int[]{1, 2, 3, 4}));
        System.out.println(maxWidthRamp(new int[]{5, 7, 4, 6, 4, 3}));
    }

    public static int maxWidthRamp(int[] arr) {
        int n = arr.length;
        int[] stack = new int[n];

        int r = 0;

        // 从左到右单调递减的放数
        // example  1: 1 2 3 4  只放 1
        // example  1: 4 2 3 1  只放 4 2 1 到栈
        for (int i = 0; i < n; i++) {
            // 栈为空 || 栈顶 > 当前数
            if (r == 0 || arr[stack[r - 1]] > arr[i]) {
                // 当前数的下标放到栈顶
                stack[r++] = i;
            }
        }

        int ans = 0;

        for (int j = n - 1; j >= 0; j--) {

            // 客栈不为空 && 栈顶的数 <= 当前数
            while (r != 0 && arr[stack[r - 1]] <= arr[j]) {
                // 可以构成坡
                // 弹出栈顶元素
                int i = stack[--r];

                // 判断当前的坡度是不是最大的坡
                ans = Math.max(ans, j - i);
            }
        }

        return ans;
    }
}
